package com.test.spring.algorithm;

import java.util.Scanner;

/**
 * 大数相乘
 *
 * @Author ll
 * @Date 2017/9/7 16:54
 */
public class BigMultiply {

    /**
     * 23451515412151511212
     * 3614844151515151515151
     * 84773573331783328327666000249636164373012
     * @param args
     */
    public static void main(String[] args) {
        BigMultiply bigMultiply = new BigMultiply();
        System.out.println("-------------输入两个大数----------------");
        Scanner scanner = new Scanner(System.in);
        String num1 = scanner.next();
        String num2 = scanner.next();
//        String result = bigMultiply.multiply3(num1, num2);
        String result = bigMultiply.multiply2(num1, num2);
//        String result = bigMultiply.multiply1(num1, num2);
        System.out.println("-------------大数相乘结果----------------");
        System.out.println(result);
        scanner.close();
    }

    /**
     * 基本思想，输入字符串，转成char数组，转成int数组。采用分治思想，每一位的相乘;
     * 公式：AB*CD = AC (BC+AD) BD , 然后从后到前满十进位(BD,(BC+AD),AC)
     *
     *
     * 52 X 34                 从后往前满十进位
     * AB * CD = AC(AD + BC)BD = 15(29)12 = 1802
     * @param num1
     * @param num2
     */
    public String multiply1(String num1, String num2) {
        //把字符串转换成char数组
        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();

        //声明存放结果和两个乘积的容器
        int[] result = new int[chars1.length + chars2.length];
        int[] n1 = new int[chars1.length];
        int[] n2 = new int[chars2.length];

        //把char转换成int数组，为什么要减去一个'0'呢？因为要减去0的ascii码得到的就是实际的数字
        for (int i = 0; i < chars1.length; i++) {
            n1[i] = chars1[i] - '0';
        }

        for (int i = 0; i < chars2.length; i++) {
            n2[i] = chars2[i] - '0';
        }

        //逐个相乘，AB*CD = AC(BC+AD)BD, 然后进位
        for (int i = 0; i < chars1.length; i++) {
            for (int j = 0; j < chars1.length; j++) {
                result[i + j] += n1[i] * n2[j];
            }
        }

        //满10进位，从后往前满十进位
        for (int i = result.length - 1; i > 0; i--) {
            result[i - 1] += result[i] / 10;
            result[i] = result[i] % 10;
        }

        //转成string并返回
        String resultStr = "";
        for (int i = 0; i < result.length - 1; i++) {
            resultStr += "" + result[i];
        }

        return resultStr;
    }

    /**
     * 基础思想是将数字转化为字符串，然后逐位相乘转化最后得出结果
     * @param num1
     * @param num2
     * @return
     */
    public String multiply2(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();

        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();

        //高低位对调
        convert(chars1, len1);
        convert(chars2, len2);

        //创建一个数组，处理相乘后的结果，两个数相乘之后的结果的位数不超过两个数的位数的和加3
        int convertSize = len1 + len2 + 3;

        //比如两个两位数相乘是定小于100*100的
        int[] convert = new int[convertSize];
        // 乘积数组填充0
        for (int i = 0; i < convertSize; i++) {
            convert[i] = 0;
        }

        //C[i+j] += A[i]*B[j]相当于10^n，从而来表示数字的位数
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                int a = Integer.parseInt(String.valueOf(chars1[i]));
                int b = Integer.parseInt(String.valueOf(chars2[j]));
                convert[i + j] += a * b;
            }
        }

        int m = 0;//高位处理
        for (; m < convertSize; m++) {
            int carry = convert[m] / 10;
            convert[m] = (char) (convert[m] % 10);
            if (carry > 0) {
                convert[m + 1] += (char) carry;
            }
        }

        // 找到最高位
        for (m = convertSize - 1; m >= 0; m--) {
            if (convert[m] > 0)
                break;
        }

        // 由最高位开始打印乘积
        for (int n = 0; n <= m; n++) {
            System.out.print(convert[m - n]);
        }

        System.out.println("\n");
        return "";
    }

    //高低位对调的目的是将各位放在数组的最前面，方便数组下标进行操作
    private static void convert(char[] chars, int len) {
        for (int i = 0; i < len / 2; i++) {
            chars[i] += chars[len - i - 1];
            chars[len - i - 1] = (char) (chars[i] - chars[len - i - 1]);
            chars[i] = (char) (chars[i] - chars[len - i - 1]);
        }
    }

    /**
     * 基本思想为多项式乘法问题，求A(x)与B(x)的乘积C(x)，朴素解法的复杂度O(n^2)，基本思想是把多项式A(x)与B(x)写成
     * A(x)=a*x^m+b
     * B(x)=c*x^m+d
     * 其中a,b,c,d为x的多项式,则A(x)*B(x)=(ac)*x^2m+(ad+bc)*x^m+bd
     * 由ad+bc=(a+b)(c+d)-ac-bd原来的4次乘法和1次加法由3次乘法和2次减法代替，减少了一次乘法操作
     * 用同样的方法应用到abcd的乘法上
     * @param x
     * @param y
     * @return
     */
    public static String multiply3(String x, String y) {
        /**
         * 基本思想是把多项式A(x)与B(x)写成A(x)=a*x^m+b B(x)=c*x^m+d
         * 其中a,b,c,d为x的多项式
         * 则A(x)*B(x)=(ac)*x^2m+(ad+bc)*x^m+bd
         * 由ad+bc=(a+b)(c+d)-ac-bd字符串模拟乘法操作
         */
        String negative = "";//正负号标识

        if ((x.startsWith("-") && y.startsWith("-")) ||
                (!x.startsWith("-") && !y.startsWith("-"))) {// x,y同为正或者同为负
            x = x.replaceAll("-", "");
            y = y.replaceAll("-", "");
            negative = "";
        } else if((x.startsWith("-") && !y.startsWith("-")) ||
                (!x.startsWith("-") && y.startsWith("-"))) {// x,y一正一负
            x = x.replaceAll("-", "");
            y = y.replaceAll("-", "");
            negative = "-";
        }

        // 如果长度都等于9，直接相乘返回
        if (x.length() == 1 && y.length() == 1) {
            // 计算乘积
            int tmp = (Integer.parseInt(x) * Integer.parseInt(y));
            if (tmp == 0) {
                return tmp + "";
            } else {
                return negative + tmp;
            }
        }

        // 公式里的abcd
        String a, b, c, d;
        if (x.length() == 1) {
            a = "0";
            b = x;
        } else {
            if (x.length() % 2 != 0) {
                x = "0" + x;
            }
            a = x.substring(0, x.length() / 2);
            b = x.substring(x.length() / 2);
        }
        if (y.length() == 1) {
            c = "0";
            d = y;
        } else {
            if (y.length() % 2 != 0) {
                y = "0" + y;
            }
            c = y.substring(0, y.length() / 2);
            d = y.substring(y.length() / 2);
        }

        // 按最大位数取值，以确定补零数目
        int n = x.length() >= y.length() ? x.length() : y.length();

        String t1, t2, t3;
        // 递归调用，根据公式计算出值
        String ac = multiply3(a, c);
        String bd = multiply3(b, d);
        t1 = multiply3(sub(a, b), sub(d, c));
        t2 = add(add(t1, ac), bd);
        t3 = add(add(Power10(ac, n),
                Power10(t2, n / 2)), bd).replaceAll("^0+", "");

        if (t3 == "") {
            return "0";
        }

        return negative + t3;
    }

    private static String add(String x, String y) {
        if (x.startsWith("-") && !y.startsWith("-")) {
            return sub(y, x.replaceAll("^-", ""));
        } else if (!x.startsWith("-") && y.startsWith("-")) {
            return sub(x, y.replaceAll("^-", ""));
        } else if (x.startsWith("-") && y.startsWith("-")) {
            return "-" + add(x.replaceAll("^-", ""), y.replaceAll("^-", ""));
        }

        if (x.length() > y.length()) {
            y = format(y, x.length(), "0");
        } else {
            x = format(x, y.length(), "0");
        }
        int[] sum = new int[x.length() + 1];
        for (int i = x.length() - 1; i >= 0; i--) {
            int tmpsum = Integer.parseInt(x.charAt(i) + "") + Integer.parseInt(y.charAt(i) + "") + sum[i + 1];
            if (tmpsum >= 10) {
                sum[i + 1] = tmpsum - 10;
                sum[i] = 1;// 表示进位
            } else {
                sum[i + 1] = tmpsum;
            }
        }

        StringBuilder returnvalue = new StringBuilder();
        for (int i : sum) {
            returnvalue.append(i);
        }

        if (sum[0] == 1) {
            return returnvalue.toString();
        } else {
            return returnvalue.replace(0, 1, "").toString();
        }
    }

    // 字符串模拟减法操作
    private static String sub(String x, String y) {
        // x是正数，y也是正数
        int flag = checkBigger(x, y);
        if (flag == 0) {
            return "0";
        } else if (flag == -1) {
            String tmp = y;
            y = x;
            x = tmp;
        }
        // 保证了x>=y
        y = format(y, x.length(), "0");// y补0与x对齐
        int[] difference = new int[x.length()];
        for (int i = x.length() - 1; i >= 0; i--) {
            int tmpdifference;
            tmpdifference = Integer.parseInt(x.charAt(i) + "") - Integer.parseInt(y.charAt(i) + "") + difference[i];
            if (tmpdifference < 0) {
                tmpdifference += 10;
                difference[i - 1] = -1;// 表示进位
            }
            difference[i] = tmpdifference;
        }
        StringBuilder returnvalue = new StringBuilder();
        for (int i : difference) {
            returnvalue.append(i);
        }
        String rv = returnvalue.toString().replaceAll("^0+", "");
        if ("".equals(rv)) {
            return "0";
        }
        if (flag == -1) {
            rv = "-" + rv;
        }
        return rv;
    }

    // 比较大小
    private static int checkBigger(String x, String y) {
        if (x.length() > y.length()) {
            return 1;
        } else if (x.length() < y.length()) {
            return -1;
        } else {
            for (int i = 0; i < x.length(); i++) {
                if (x.charAt(i) > y.charAt(i)) {
                    return 1;
                } else if (x.charAt(i) < y.charAt(i)) {
                    return -1;
                }
            }
            return 0;
        }
    }

    //数据前补零
    private static String format(String str, int len, String fu) {
        len = len - str.length();
        for (int i = 0; i < len; i++) {
            str = fu + str;
        }
        return str;
    }

    // 模拟移位
    public static String Power10(String num, int n) {
        for (int i = 0; i < n; i++) {
            num += "0";
        }
        return num;
    }
}
